The interplay between mutation and selection plays a fundamental role in the behavior of evolutionary algorithms (EAs). However, this interplay is still not completely understood. This paper presents a rigorous runtime analysis of a non-elitist population-based EA that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter $\eta$, controlling the selection pressure in linear ranking, and parameter $\chi$ controlling the bit-wise mutation rate, impacts the runtime of the algorithm. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which can only be solved in polynomial time if the ratio between parameters $\eta$ and $\chi$ is within a narrow critical interval, and where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown quantitatively how the appropriate parameter choice depends on the characteristics of the fitness function. In addition to the original results on the runtime of EAs, this paper also introduces a very useful analytical tool, i.e., multi-type branching processes, to the runtime analysis of non-elitist population-based EAs.
展开▼
机译:突变和选择之间的相互作用在进化算法(EA)的行为中起着基本作用。但是,这种相互作用仍然没有被完全理解。本文对使用线性排名选择机制的非精英人群基于EA的系统进行了严格的运行时分析。分析着重于控制线性排序中选择压力的参数$ \ eta $和控制逐位突变率的参数$ \ chi $之间的平衡如何影响算法的运行时间。结果指出了在选择压力和变异率之间保持正确平衡对于在多项式时间内找到最佳解至关重要的情况。特别地,表明存在适应度函数,仅当参数$ \ eta $和$ \ chi $之间的比率在狭窄的临界区间内时,才能在多项式时间内求解,并且该比率的微小变化会增加运行时间呈指数增长。此外,定量显示了合适的参数选择如何取决于适应度函数的特征。除了关于EA运行时的原始结果之外,本文还为非精英人群EA的运行时分析引入了一种非常有用的分析工具,即多类型分支过程。
展开▼